#!/usr/bin/python

import math
import sys
import itertools

FLOAT_COMPARISON_EPSILON = 1e-8

def parse_input_file(filename):
    lines = open(filename).readlines()
    def parse_line(line):
        elements = [float(x) for x in line.split()]
        return zip(elements[0::2], elements[1::2])
    return (parse_line(lines[1]), parse_line(lines[3]))

def find_center_point(points):
  """Center point is the center of gravity: average of all points."""
  return (sum(p[0] for p in points)/float(len(points)), sum(p[1] for p in points)/float(len(points)))

def calc_displace_vector(vertex, center):
  return tuple(v-c for c, v in zip(vertex, center))

def displace_edge(edge, displace_vector):
  return tuple(tuple(e+d for e, d in zip(v, displace_vector)) for v in edge)

def find_perpendicular(line):
  """Assumes that lines are edges of the polygon drawn clockwise."""
  p1, p2 = line
  if p1[0] == p2[0]:
    return 0 if p1[1] > p2[1] else math.pi
  m, _ = find_m_n(line)
  additive_pi = 0.5*math.pi if p2[0] > p1[0] else 1.5*math.pi
  return (math.atan(m) + additive_pi) % (2*math.pi)

def find_closest_vertex(p, q):
  """Returns a list of (q_edge, p_vertex) pairs."""
  q_perps = sorted((-find_perpendicular(e), e) for e in zip(q, list(q[1:]) + [q[0]]))
  p_perps = sorted((-find_perpendicular(e), e) for e in zip(p, list(p[1:]) + [p[0]]))
  i = 0
  l = []
  for angle, edge in q_perps:
    while i < len(p_perps) and (p_perps[i][0] < angle):
      i += 1
    l.append((edge, p_perps[i % len(p_perps)][1][0]))
  return l

def displace_by_closest_vertex(edge_with_closest_vertex, p_center):
  l = []
  for edge, closest_vertex in edge_with_closest_vertex:
    l.append(displace_edge(edge, calc_displace_vector(closest_vertex, p_center)))
  return l

def find_m_n(line):
  """Finds the m, n which are in y=mx*n of the given line, None for both if line is vertical."""
  p1, p2 = line
  if p1[0] == p2[0]: return None, None
  m = (p2[1]-p1[1])/(p2[0]-p1[0])
  n = p2[1]-m*p2[0]
  return m, n

def intersect_two_lines(l1, l2):
  m1, n1 = find_m_n(l1)
  m2, n2 = find_m_n(l2)

  # Lines are parallel
  if m1 == m2:
    return None

  # One of the lines is vertical
  if m1 is None:
    l1, l2, m2, n2, m1, n1 = l2, l1, m1, n1, m2, n2
  if m2 is None:
    return (l2[0][0], m1*l2[0][0]+n1)

  x = (n2-n1)/(m1-m2)
  return (x, m1*x+n1)

def has_left_turn(v1, v2, v3):
   return (v2[0]-v1[0])*(v3[1]-v1[1]) - (v2[1]-v1[1])*(v3[0]-v1[0]) > FLOAT_COMPARISON_EPSILON

def compare_vertices(v1, v2):
  return abs(v1[0]-v2[0]) < FLOAT_COMPARISON_EPSILON and abs(v1[1]-v2[1]) < FLOAT_COMPARISON_EPSILON

def sort_and_remove_same_vertices(vertices):
  vertices = sorted(vertices)
  i = 0
  while i < len(vertices)-1:
    i += 1
    if compare_vertices(vertices[i], vertices[i-1]):
      del vertices[i]
      i -= 1
  return vertices

def order_vertices(vertices_set):
  vertices = sort_and_remove_same_vertices(vertices_set)
  i = 0
  top = []
  while i < len(vertices):
    top.append(vertices[i])
    if len(top) >= 3 and has_left_turn(*top[-3:]):
      del top[-2:]
    else:
      i += 1
  bottom_set = set(vertices) - set(top)
  bottom = sorted(bottom_set, reverse=True)
  return top + bottom
    
def find_new_polygon(edges):
  """Intersects edges to find new inner polygon."""
  vertices = set()
  for l1, l2 in itertools.product(edges, edges):
    if l1 == l2:
      continue
    intersection = intersect_two_lines(l1, l2)
    if intersection is None:
      continue
    vertices.add(intersection)
  for edge, vertex in itertools.product(edges, vertices):
    if has_left_turn(edge[0], edge[1], vertex) and vertex in vertices:
      vertices.remove(vertex)
  return order_vertices(vertices)

def critical_inner_polygon(p, q):
    """
    Input
        p - The 'robot' polygon
        q - The 'maze' polygon
    Output
        An array of 2-tuples of x,y of the critical path of the inner polygon
    """
    edge_with_closest_vertex = find_closest_vertex(p, q)
    displaced_edges = displace_by_closest_vertex(edge_with_closest_vertex, find_center_point(p))
    new_polygon = find_new_polygon(displaced_edges)
    return new_polygon

def is_clockwise_poly(p):
    for triplet in zip(p, p[1:] + p[0:1], p[2:] + p[0:2]):
        if has_left_turn(*triplet):
            return False
    return True
    
def main(args):
  if len(args) != 2:
    print "Usage: %s <filename>" % args[0]
    return
  p, q = parse_input_file(args[1])
  if not is_clockwise_poly(p):
      print "Robot polygon is not clockwise"
      return
  if not is_clockwise_poly(q):
      print "Maze polygon is not clockwise"
      return
  res_polygon = critical_inner_polygon(p, q)
  if res_polygon is None:
    print "No free space!"
  else:
    print len(res_polygon)
    print " ".join("%s %s" % (x, y) for x, y in res_polygon)

if __name__ == "__main__":
  main(sys.argv)
